Notably, for each Communication Protocol, an Incoming Address Space (the maximum number of channels a specific protocol can handle) is defined. In this document reference is made to the so-called addressing space of 2N bits as the set of Incoming Addresses.
On the other hand, a telecom equipment is able to deal only with some managed channels. The number of simultaneously manageable channels is finite and is a typical design target. Each managed channel must be addressable by means of an internal identifier, that is a subset of the Incoming Address. In this document reference is made to the space of 2Ncpr bits of the internal identifiers as the set of Compressed Addresses.
In a telecom equipment, a function mapping some points belonging to the universe of Incoming addresses (2N bits) to a set of Compressed Identifiers (2Ncpr bits) should be implemented. This function is called the Address Compression Function.
Due to network management reasons, the Incoming Address Space is very large. On the other hand, the number of channels that must be managed simultaneously nowadays by telecommunication apparatuses is also very large. Moreover, data link speed is increasing at an impressive pace: in ten years from 64 Kbit/s to 155 Mbit/s and now to 1.2 Gbit/s.
Because of this, the efficiency of the design of the Address Compression Function is today a key factor in equipment like routers and switches. Altogether, designing has become critical because, due to the increased data speed, the time that can be spared to perform the Address Compression Function is reduced. On the other hand, the increasing number of manageable channels augments costs because of the increasing number of resources needed to perform the Address Compression Function.
1.1.1 Address Compression Problem Definition
The aim of the algorithm is to compress a defined set of addresses S, the set of addresses to be compressed, belonging to the set U, the whole addressing space, as shown in FIG. 1. For each of these addresses the algorithm must identify one and only one address belonging to C, the set of compressed address (i.e. perform a transformation Sxe2x86x92C).
n dimension of the whole addressing space (Uxe2x89xa1{a0, . . . , a2n})
ncpr dimension of the space of compressed addresses (Cxe2x89xa1{a0, . . . , a2ncpr})
where: ncpr less than n, C⊂U.
The cardinality of S must equals the cardinality of C.
1.1.2 Address Compression Function and IP Application
The most fundamental operation in any IP routing product is the Routing Table search process.
A packet is received with a specific Destination Address (DA), identified by a unique 32-bit field in current IP Version 4 implementations. The router must search a forwarding table using the IP Destination Address as its key and determine which entry in the table represents the best route for the packet to take in its journey across the network to its destination.
A  less than  less than flat greater than  greater than  forwarding table would have a size of 232 addresses, that means 4 Gbytes of address space (16 Gbytes of data). The DA must be compressed to point to a reasonable table size.
The route search operation is the single most time-consuming operation that must be performed in routers today, and typically defines the upper bound, on the router""s ability to forward packets.
The problem has grown even more challenging in recent years.
Data links now operate routinely at 100 MBits/second, and generate nearly 150,000 packets-per-second requiring routing.
New protocols, such as RSVP, require route selection based not only on Destination Address, but potentially also Protocol Number, Source Address, Destination Port and Source Port.
IP Version 6 will increase the size of the address field from 32 bits to 128 bits, with network prefixes up to 64 bits in length. Expanded use of IP Multicasting requires that searches include large numbers of Class D (Multicast Group) addresses with large numbers of users.
Moreover, the ever-expanding number of networks and hosts on Internet is making routing table sizes larger and larger.
1.1.3 Address Compression Function and ATM Applications
ATM data equipment, to be compliant with ITU and ATM-forum specifications, must be able to receive ATM cells for any admissible value of the header fields VPI.VCI. The total length of these fields is 24 bits (16.7 millions of admissible values).
On the other hand, the ATM equipment is designed to manage a number of internal channels (at least) equal to the maximum number of engageable channels. This number depends on the application: from one to hundreds in the case of terminals; some thousands (4K, 64K) in case of core network equipment.
In the following description, the univocal (shorter) internal channel identifier, will be referred to as Channel Identifier (CID).
It is evident the requisite that the processing be able to map from any possible value of VPI.VCI (24 bits) to any possible CID (e.g. 12 bits).
A compression function able to map from a string of length N bits to a (unique) string of length Ncpr (Ncpr less than N) can be implemented in various ways.
Two main classes exist: the algorithms with an unpredictable duration belong to a first class; the others, with a predictable duration, belong to the second one.
For those belonging to the first class, it is not possible to know for how much time (microprocessor instructions or clock cycles) the algorithm will run before hitting the compressed identifier. It will depend on the number of active connections. These algorithms are normally easier to implement, do not require lots of resources and can be sped-up only by improving RAM access time of the memories where the search tables are located.
For the algorithms of the second class, (predictable duration algorithms) it is possible to know, UNDER ANY CONDITION, how much time (microprocessor instructions or clock cycles) the algorithm will run before hitting the compressed identifier. These algorithms often require a lot of resources.
An algorithm belonging to the second class ensures that the maximum search time is less than the time used to receive the shortest packet1, this guarantees the maximum allowable throughput of the equipment.
164 bytes for IP, 53 bytes for ATM 
1.2.1 Unpredictable Duration Algorithms
IP routers companies have developed the algorithms belonging to this class some years ago. It is possible to call them  less than  less than classical route search techniques greater than  greater than . The main algorithms will be explained for an IP context to provide the reader with useful historical background.
1.2.1.1 The Patricia Tree
This is the most popular algorithm used in router xe2x80x9cslow pathsxe2x80x9d. The forwarding table, (associating each prefix entry with an exit port and next-hop MAC address) is stored in a xe2x80x9cBinary Root Treexe2x80x9d form.
The table is organized in a series of xe2x80x9cnodesxe2x80x9d, each of which contains a route of different length, and each of which has two xe2x80x9cbranchesxe2x80x9d to subsequent nodes in the tree. At the ends of the branches there are xe2x80x9cleavesxe2x80x9d, which either represent full 32-bit host routes (for devices attached directly to the router) or most-specific routes available to a particular subnet.
The algorithm is able to map ANY incoming vector to a unique outcoming identifier. Unfortunately, in the worst case, the algorithm will have to travel all the way to the end of the tree to find a leaf, and the time needed cannot be absolutely predictable.
The Patricia Tree approach does not scale well to level-2 packet switching: a worst-case lookup involves a large number of memory accesses, taking far more time than that available at gigabit rates. Moreover, hardware implementation is rather complex. This algorithm was developed for general-purpose software implementations.
1.2.1.2 Hashing Tables
xe2x80x9cHashingxe2x80x9d is an alternative approach. Unlike the Patricia Tree, hashing operates strictly on an exact-match basis, and assumes that the number of  less than  less than channels greater than  greater than  (IP Destination Addresses, VPI/VCIout) the system must handle at any one time be limited to a few thousands.
A xe2x80x9chashxe2x80x9d functionxe2x80x94a sort of compression algorithmxe2x80x94is used to condense each incoming identifier (24 or 32 bits) in the table to a smaller-sized entry (8-10 bits typically).
When a packet is received, an equivalent xe2x80x9chash valuexe2x80x9d is computed quickly from its incoming identifier. This value points to a hash table (named a xe2x80x9cslotxe2x80x9d) that corresponds to one or more outcoming identifiers. The compression effected by a hashing function makes the table small enough to be quickly searched sequentially using simple hardware-based exact matching techniques.
The main problem involved in the hashing technique is that it assumes a  less than  less than flat greater than  greater than  distribution of the values of incoming identifiers. The  less than  less than hash greater than  greater than  function maps the space of possible values of incoming identifier in a plurality of sub-spaces.
In FIG. 2, the ellipse indicates the U space and the incoming valid identifiers, that is the S space, are indicated as tiny circles. The  less than  less than hash greater than  greater than  function generates the boundaries between sub-spaces. If, as depicted in FIG. 3, in a sub-space a number of identifiers greater than the slot size (hash table) must be mapped, it is necessary to recalculate anew the hash function in an appropriate way.
This involves item sorting in hash tables that cannot be performed in a real time mode.
This process is easy to implement in hardware and tends to perform fairly well, albeit in a probabilistic manner.
Unfortunately there are a number of drawbacks with this algorithm. In a hardware implementation it is not possible to change  less than  less than on the fly greater than  greater than  the  less than  less than hash greater than  greater than  function, because a full item sorting is implied. This means that the only way to overcome the problem is to increase the slot length, but obviously this is not always possible.
The main ATM IC developers (Motorola, IDT, Transwitch) have implemented an algorithm of this kind. A typical architecture is shown in FIG. 4
A main problem is that the incoming identifier processing time is not deterministic (in some case a sequential search is needed) and eventually will become longer than one packet (cell) time).
The ACF function is implemented by means of several readings in the Hash tables that are written by the controlling microprocessor in a xe2x80x9coff-linexe2x80x9d manner.
The algorithm implies the subtle assumption that the sequence of incoming identifiers be  less than  less than spread greater than  greater than  on the entire set of sub-spaces and that in any sub-space the average search time be shorter than the packet (cell) time.
Moreover, use of a quite long fifo (10, 20 packets/cell positions) is required in order to decouple the incoming rate speed from the speed of the compression algorithm, that in the average would be the same.
In some cases, it may happen that the packet (cell) is lost or misrouted. The only way to cure this problem is to increase the speed of the hash table2.
2 For example, the Motorola ATMC devices needs 10 nS hash memories. 
This architecture is preferred by NIC chip providers because is cheaper, but it is unable to support the mapping of any possible incoming identifier to local identifiers.
In the present context sometimes use is made of different expression for indicating materially the same thing. In particular the same N-bit string or the same Ncpr-bit string is often referred to with the expressions: physical layer identifier, virtual path identifier address, vector. These are expression that are commonly used and perfectly understand by technicians and the different expressions are often used when describing an algorithm or a data processing structure, and so forth.
1.2.2 Predictable Duration Algorithms
In predictable duration algorithms, the ACF is performed under any condition in a time that may be less than or even equal to the packet time (cell period). A typical architecture is shown in FIG. 5.
Because the algorithm duration may be knowingly shorter than a packet (cell) cycle, it is possible to admit ANY type of incoming traffic. On the other hand, more chip or system resources are needed to implement the function than those do that would be required by an algorithm of unpredictable duration.
There are three well-known techniques that are able to perform ACF predictably in less than one packet (cell):
CAM
Sequential search
Binary tree
1.2.2.1 CAM
According to this approach, the incoming address (e.g. VPI.VCI) is input to a Context Access Memory. The CAM hits the correct compressed. If there is no hit the cell is discarded.
The CAM is wide as the incoming address and is deep enough to accommodate the maximum number of connections.
The time of execution of the ACF is typically of few clock cycles. It is in any case less then a cell time. The main problem of this architecture is the availability of the CAM module3.
3 On the market, there is a component that implements CCF function in this manner. It is the Fujitsu MB86689 Address Translation Controller (ATC) 
1.2.2.2 Sequential Search
To obtain a compressed identifier from an incoming address, it is possible to perform a sequential search on a RAM, for a number of cycles less or equal the packet (cell) time. A relatively small RAM, a counter to generate addresses and a unique 24-bit comparator is all is needed, as depicted in FIG. 6.
1.2.2.3 Extended Sequential Search
To increase the extent of the sequential search without exceeding the number of available clock cycles, it is possible to use several RAMs, several counters to generate the addresses, several 24-bit comparators and a priority encoder, as depicted in FIG. 7.
1.2.2.4 Binary Tree
The mapping from the valid incoming vectors to the compressed identifier is implemented by means of a chain of memories.
A pointer chain link has to be written in these memories in order to link any valid incoming vector with the right compressed identifier
The first memory is addressed by a bit slice of the incoming address (typically the most significant bits). The content is a pointer to the second one.
The second memory is addressed by the pointer obtained from the first one, chained with a new slice belonging to the incoming vector. The content is a pointer to the third one.
The third memory is addressed by the pointer obtained from the second one, chained with another slice belonging to the incoming vector. The chain ends when any bit belonging to the incoming address has been used.
In order to ensure a no-blocking probability, the wide of any memory has to be equal to Ncpr.
Unfortunately, because of this, the memory utilization is really poor (around 5,10%).
FIG. 8 shows the organization of the memories needed for implementing a Binary Tree Search.
In FIG. 9 the ellipse depicts the U space and the set of incoming valid identifiers, the S space is indicated by the tiny circles. The Binary Tree technique splits the U space in areas of equivalent size, by means of a direct addressing table or DAT; then the sub-spaces are split again, by means of RTis, in order to ensure that no more than a point belonging to S is present in a particular sub-space.
FIG. 10 shows a typical implementation related to ATM words of 24 bits of incoming VPI.VCI that must be converted to proper channel identifiers CID, 12 bits wide. The basic assumption is to implement a research path on some external RAM bank, addressed by means of VPI.VCI fields.
Four banks (ATM Compression Blocks) of RAM are addressed for a total amount of 392 Kbytes, in order to have up to 4096 different CIDs. Four addressing cycles are needed. The dimensions of the memories depend on the maximum number of CDs needed.
U.S. Pat. No. 5,414,701 describes a method and a structure for performing address compression in an ATM system according to a so-called content addressable memory (CAM) as described above.
Standing the requisite of performing the required mapping of incoming N-bit identifiers into Ncpr-bit virtual path identifiers within a cell time slot, the implementation of a consequent data processing structure for performing such an address compression function, following one of the known approaches as the ones reviewed above, implies the use of a relatively large amounts of physical resources in terms of RAM memories.
Irrespectively, of the approach followed, the RAM requisite for a reliable operation of the data processing structure employed for performing address compression represents a crucial cost factor and it is evident the opportunity of finding methods of performing the address compression more efficient than the presently known ones and that may be realized at a reduced cost.
It has now been found a method of address compression outstandingly more efficient than the known methods, capable of reducing the RAM requisite for comparable performances in terms of number of clock cycles necessary to complete the compression algorithm.
Moreover, when assuming an optimization of the data processing structure of the invention, the performance in terms of the two parameters of memory requisite and of number of clock cycles required, is significantly better than the performance obtainable from any of the systems realized according to the known approaches.
These important advantages are achieved, according to the present invention, by a method that combines certain aspects of an unpredictable duration algorithm with those of a classical sequential search algorithm. The synergistic combination of different approaches produces the reported outstanding performance.
Basically, the method of the invention combines the splitting of the incoming address space (U) into a plurality of sub-spaces, a tree search algorithm for clustering a defined set (S) of identifiers contained in the sub-spaces into which the incoming addresses space (U) has been split.
Having so clustered the elements of the defined set (S) of identifiers, a sequential search is performed within each cluster so constructed for identifying the Ncpr-bit identifier belonging to the compressed address space (C).
By performing the sequential search so restricted over a pre-identified cluster of a known size, ensures identification within a given number of clock cycles (a predictable time span). The system may be further optimized for either reducing the number of clock cycles required by the sequential search or for reducing the memory requisite.
The method of the invention is more precisely defined, respectively, in the independent claims 1 and 6 for a unclassified address space and preferred embodiments are defined in claims 2 and 5, while the data processing structure of the invention that implements the method is defined in the appended claims 7 and 12 for a classified address space, and preferred embodiments in claims 8 to 11.